package com.fosss.huffmanCode;

import java.io.*;
import java.util.*;

/**
 * 赫夫曼编码及压缩解压字节数组
 */
public class HuffmanCode {
    public static void main(String[] args) {
        String content = "i like like like java do you like a java";
        byte[] contentBytes = content.getBytes();

        List<Node> list = getNodes(contentBytes);
//        System.out.println(nodes);
        Node root = createHuffmanTree(list);
        preOrder(root);

        //获取赫夫曼编码
        getCodes(root, "", stringBuilder);
        System.out.println(codeMap);

        Map<Byte, String> codes = getCodes(root);
        System.out.println(codes);

//         * 测试压缩后的字节数组



        byte[] zip = zip(contentBytes, codes);
        System.out.println(zip.length);

        System.out.println("初始字节数组：" + Arrays.toString(contentBytes));
        System.out.println("初始长度：" + contentBytes.length);
        System.out.println("-------------------");
        //用封装后的方法进行压缩进行压缩
        byte[] bytes = huffmanZip(contentBytes);
        System.out.println("压缩后的字节数组：" + Arrays.toString(bytes));
        System.out.println("压缩后的长度：" + bytes.length);
/**
         * 测试解压缩
         */

        System.out.println(byteToBitString(false, (byte) -1));
        System.out.println(byteToBitString(true, (byte) 1));
        byte[] decode = decode(codes, zip);
        System.out.println(new String(decode));


        /**
         * 测试压缩文件
         */
//        String srcFile="D:\\a.bmp";
//        String destFile="D:\\a.zip";
//        zipFile(srcFile,destFile);
//        System.out.println("压缩文件成功！");
        /**
         * 测试解压文件
         */
        String srcFile="D:\\a.zip";
        String destFile="D:\\a2.bmp";
        deCodeFile(srcFile,destFile);
        System.out.println("解压文件成功！");
    }

    /**
     * 实践：解压文件
     * @param srcFile 待解压的文件路径
     * @param destFile 解压后的路径
     */
    public static void deCodeFile(String srcFile, String destFile){
        FileInputStream is=null;
        ObjectInputStream ois = null;
        FileOutputStream os=null;

        try {
            is=new FileInputStream(srcFile);
            ois=new ObjectInputStream(is);
            //压缩后的文件
            byte[] zipFile = (byte[]) ois.readObject();
            //获取赫夫曼编码
            Map<Byte,String> huffmanCodes = (Map<Byte, String>) ois.readObject();
            //进行解压
            byte[] decode = decode(huffmanCodes, zipFile);
            os=new FileOutputStream(destFile);
            os.write(decode);

        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                is.close();
                ois.close();
                os.close();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

    /**
     * 实践：压缩文件
     *
     * @param srcFile  源文件的存放位置
     * @param destFile 压缩后的存放位置
     */
    public static void zipFile(String srcFile, String destFile) {

        //创建输入流读取源文件
        FileInputStream is = null;
        //创建输出流写文件
        FileOutputStream os = null;
        ObjectOutputStream oos = null;
        try {
            is = new FileInputStream(srcFile);
            byte[] bytes=new byte[is.available()];
            is.read(bytes);

            //进行压缩
            byte[] huffmanZip = huffmanZip(bytes);

            os=new FileOutputStream(destFile);
            //创建对象输出流是为了解码
            oos = new ObjectOutputStream(os);
            oos.writeObject(huffmanZip);
            //为了解码，需要将赫夫曼编码写入压缩文件
            oos.writeObject(codeMap);

        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                is.close();
                os.close();
                oos.close();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

    }

    /**
     * !!!!!!!!!!!!!!!!!!!!以下是进行解压缩的过程
     */


    /**
     * 完成对压缩数据的解码
     *
     * @param huffmanCodes 赫夫曼编码表 map
     * @param huffmanBytes 赫夫曼编码得到的字节数组
     * @return 就是原来的字符串对应的数组
     */
    private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {

        //1. 先得到 huffmanBytes 对应的 二进制的字符串 ， 形式 1010100010111...
        StringBuilder stringBuilder = new StringBuilder();
        //将byte数组转成二进制的字符串
        for (int i = 0; i < huffmanBytes.length; i++) {
            byte b = huffmanBytes[i];
            //判断是不是最后一个字节
            boolean flag = (i == huffmanBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag, b));
        }

//        System.out.println("解码后的字符串："+stringBuilder);
//        return null;

        //把字符串安装指定的赫夫曼编码进行解码
        //把赫夫曼编码表进行调换，因为反向查询 a->100 100->a
        Map<String, Byte> map = new HashMap<>();
        Set<Map.Entry<String, Byte>> entries = map.entrySet();
        for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }

        //将字符串转为byte数组
        //创建list集合用来存放bytes
        List<Byte> list = new ArrayList<>();
        for (int i = 0; i < stringBuilder.length(); ) {
            int count = 1;
            while (true) {
                String key = stringBuilder.substring(i, i + count);
                Byte b = map.get(key);
                if (b == null) {
                    //map中不存在这个编码
                    count++;
                } else {
                    list.add(b);
                    break;
                }
            }
            i += count;
        }
        //将list中的字节存储到byte数组中
        byte[] bytes = new byte[list.size()];
        for (int i = 0; i < bytes.length; i++) {
            bytes[i] = list.get(i);
        }
        return bytes;
    }

    /**
     * 将一个byte转为二进制字符串
     *
     * @param flag 表示是否是最后一个字节
     * @param b    已经压缩的字节数组
     * @return 转化后的二进制字符串
     */
    private static String byteToBitString(boolean flag, byte b) {
        //将byte类型转为int类型，在利用Integer自带的方法转为字符串，
        //这里需要注意int类型为4个字节，32位，而byte类型只有八位
        int temp = b;

        //判断要进行转化的字节是负数还是正数，正数(不是最后一位)需要补位（到8），负数需要截取（32->8）
        if (flag && temp > 0) {
            //不是最后一个字节并且是正数,按位或来补位
            temp |= 256;
        }
        //转化为二进制字符串
        String str = Integer.toBinaryString(temp);
        if (flag || temp < 0) {
            //不是最后一位或者temp小于零
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }


    /**
     * !!!!!!!!!!!!!!!!!!!以下是进行数据压缩的方法
     */

    /**
     * 对整个赫夫曼压缩的所有子功能进行一个封装
     *
     * @param bytes 初始的字节数组
     * @return 压缩后的字节数组
     */
    private static byte[] huffmanZip(byte[] bytes) {
        //创建结点集合
        List<Node> nodes = getNodes(bytes);
        //创建赫夫曼树
        Node huffmanTree = createHuffmanTree(nodes);
        //创建编码集合
        Map<Byte, String> codes = getCodes(huffmanTree);
        //进行压缩
        byte[] zip = zip(bytes, codes);
        return zip;
    }

    /**
     * 获取压缩后的字节数组
     *
     * @param bytes        压缩前的字节数组
     * @param huffmanCodes 赫夫曼编码
     * @return 压缩后的字节数组
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : bytes) {
            String s = huffmanCodes.get(b);
            stringBuilder.append(s);
        }
//        System.out.println("编码字符串："+stringBuilder);

        //将字符串转为字节数组

        int len;//字节数组的大小
        if (stringBuilder.length() % 8 == 0) {
            len = stringBuilder.length() / 8;
        } else {
            len = stringBuilder.length() / 8 + 1;
        }
        byte[] huffmanCodesBytes = new byte[len];
        int index = 0;

        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String substring;
            if (i + 8 > stringBuilder.length()) {
                //不够8位，有多少位取多少位
                substring = stringBuilder.substring(i);
            } else {
                substring = stringBuilder.substring(i, i + 8);
            }

            huffmanCodesBytes[index] = (byte) Integer.parseInt(substring, 2);
            index++;

        }

        return huffmanCodesBytes;
    }

    /**
     * 为了调用方便，重载getCodes方法
     *
     * @param root 传入的根结点
     * @return 返回赫夫曼编码集合
     */
    private static Map<Byte, String> getCodes(Node root) {
        if (root == null) {
            System.out.println("赫夫曼树为空");
        } else {
            getCodes(root, "", stringBuilder);
        }
        return codeMap;
    }

    /**
     * 创建Map结合存储赫夫曼编码
     */
    static Map<Byte, String> codeMap = new HashMap<>();

    /**
     * 用于字符串拼接
     */
    static StringBuilder stringBuilder = new StringBuilder();

    /**
     * 生成赫夫曼树对应的赫夫曼编码
     *
     * @param root 根结点
     * @param code 路径编码 0代表左子节点，1代表右子节点
     * @param sb   用于字符串拼接
     */
    private static void getCodes(Node root, String code, StringBuilder sb) {
        //拼接路径编码
        StringBuilder stringBuilder2 = new StringBuilder(sb);
        stringBuilder2.append(code);
        //node为空时不进行操作
        if (root != null) {
            //判断是不是叶子结点
            if (root.data == null) {
                //不是叶子节点
                //向左递归
                getCodes(root.left, "0", stringBuilder2);
                //向右递归
                getCodes(root.right, "1", stringBuilder2);
            } else {
                //是叶子节点，将数据存储到map集合中
                codeMap.put(root.data, stringBuilder2.toString());
            }
        }
    }

    /**
     * 前序遍历
     */
    private static void preOrder(Node root) {
        if (root == null) {
            System.out.println("赫夫曼树为空");
        } else {
            root.preOrder();
        }
    }

    /**
     * 创建赫夫曼树
     *
     * @param list 集合
     * @return 返回根结点
     */
    private static Node createHuffmanTree(List<Node> list) {
        while (list.size() > 1) {
            //排序
            Collections.sort(list);

            Node leftNode = list.get(0);
            Node rightNode = list.get(1);
            //父结点的data中不存数据，数据都存在叶子结点中
            Node parent = new Node(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;

            //从list中移除，添加结点
            list.remove(leftNode);
            list.remove(rightNode);
            list.add(parent);
        }
        return list.get(0);
    }

    /**
     * 获取存有结点数据的集合
     *
     * @param bytes 字节码
     * @return 返回集合
     */
    private static List<Node> getNodes(byte[] bytes) {
        ArrayList<Node> list = new ArrayList<>();

        Map<Byte, Integer> map = new HashMap<>();

        for (Byte aByte : bytes) {
            Integer count = map.get(aByte);
            if (count == null) {
                map.put(aByte, 1);
            } else {
                map.put(aByte, count + 1);
            }
        }

        /**
         * 遍历map集合，将数据存储到list集合中
         */
        Set<Map.Entry<Byte, Integer>> entries = map.entrySet();
        for (Map.Entry<Byte, Integer> entry : entries) {
            Node node = new Node(entry.getKey(), entry.getValue());
            list.add(node);
        }
        return list;
    }

}

/**
 * 创建结点类
 */
class Node implements Comparable<Node> {
    /**
     * 存储编码值
     */
    public Byte data;
    /**
     * 存储权值
     */
    public int weight;
    public Node left;
    public Node right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }

    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}




















